﻿#include <iostream>

static int recur(const char* text, int index)
{
    if (index <= 0) return 0;

    char cur = text[index];
    if (cur == '(') return 0;

    int prev = recur(text, index - 1);
    int count = 0;
    if (text[index - prev - 1] == '(')
    {
        count += prev;
        count += 2;
        count += recur(text, index - prev - 2);
    }

    return count;
}

#define MAX(a, b) (a > b ? a : b)

static int byStrictTable(const char* text)
{
    size_t size = strlen(text);
    int* dp = (int*)malloc(size * sizeof(int));
    memset(dp, 0, size * sizeof(int));
    int validLength = 0;
    for (int i = 0; i < size; i++)
    {
        if (text[i] == '(' || i == 0) continue;

        int prev = dp[i - 1];
        int count = 0;
        if (text[i - prev - 1] == '(')
        {
            count += prev + 2;
            if (i - prev - 2 >= 0)
                count += dp[i - prev - 2];
        }

        dp[i] = count;
        validLength = MAX(dp[i], validLength);
    }

    free(dp);
    return validLength;
}

//  给一个括号匹配序列，求其中的最长的有效子串。
//  比如: "())()(())()))(())", 最长的有效子串是
//  ())()(())()))(())
//  ________
//  即: "()(())()"
// 
// 可以求出以每个字符结尾的情况下，有效的字符串的长度是什么，最终的答案取所有长度的最大值即可。
// 
//  ( ) ) ( ) ( ( ) ) (  )  )  )  (  (  )  )
//  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
//  dp: []
// 
// dp[i] : 子串必须以i位置结尾，最长的有效长度是多少 ?
// 
// 1. 如果第i个字符是'(', 那么这个子串必定无效，dp[i] = 0；
// 2. dp[i]可以使用dp[i - 1]推出，假设dp[i - 1] = 4, 则看第i - 5字符是不是'('，如果是，则dp[i]至少 是4 + 2;
// 但是在第i - 5之前也可能是有效的子串，故需要再加dp[i - 6]的值，则dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 1 - 1];
// 如果不是，则dp[i] = 0
int main_LongestValidSubString()
{
    char text[256] = "())()(())()))(())";
    size_t size = strlen(text);
    int validLength = 0;
    for (int i = 0; i < size; i++)
    {
        int r = recur(text, i);
        validLength = MAX(validLength, r);
    }

    printf("%d\n", validLength);
    validLength = byStrictTable(text);
    printf("%d\n", validLength);
    return 0;
}